|
In combinatorial mathematics, the Albertson conjecture is an unproven relationship between the crossing number and the chromatic number of a graph. It is named after Michael O. Albertson, a professor at Smith College, who stated it as a conjecture in 2007;〔According to , the conjecture was made by Albertson at a special session of the American Mathematical Society in Chicago, held in October 2007.〕 it is one of his many conjectures in graph coloring theory.〔.〕 The conjecture states that, among all graphs requiring ''n'' colors, the complete graph ''K''''n'' is the one with the smallest crossing number. Equivalently, if a graph can be drawn with fewer crossings than ''K''''n'', then, according to the conjecture, it may be colored with fewer than ''n'' colors. ==A conjectured formula for the minimum crossing number== It is straightforward to show that graphs with bounded crossing number have bounded chromatic number: one may assign distinct colors to the endpoints of all crossing edges and then 4-color the remaining planar graph. Albertson's conjecture replaces this qualitative relationship between crossing number and coloring by a more precise quantitative relationship. Specifically, a different conjecture of states that the crossing number of the complete graph ''K''''n'' is : It is known how to draw complete graphs with this many crossings, by placing the vertices in two concentric circles; what is unknown is whether there exists a better drawing with fewer crossings. Therefore, a strengthened formulation of the Albertson conjecture is that every ''n''-chromatic graph has crossing number at least as large as the right hand side of this formula.〔.〕 This strengthened conjecture would be true if and only if both Guy's conjecture and the Albertson conjecture are true. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Albertson conjecture」の詳細全文を読む スポンサード リンク
|